//203：移除链表元素
//给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
//
//
// 示例 1：
//
//
//输入：head = [1,2,6,3,4,5,6], val = 6
//输出：[1,2,3,4,5]
//
//
// 示例 2：
//
//
//输入：head = [], val = 1
//输出：[]
//
//
// 示例 3：
//
//
//输入：head = [7,7,7,7], val = 7
//输出：[]
//
//
//
//
// 提示：
//
//
// 列表中的节点数目在范围 [0, 10⁴] 内
// 1 <= Node.val <= 50
// 0 <= val <= 50
//
// Related Topics 递归 链表 👍 919 👎 0
//TODO 這題有坑

//leetcode submit region begin(Prohibit modification and deletion)
//  Definition for singly-linked list.


public class RemoveElements {
    public ListNode removeElements(ListNode head, int val) {

        //先处理头节点需要删除的情况
        while (head != null && head.val == val) {
            head = head.next;
        }
        if (head == null) {
            return null;
        }
        //指针p
        ListNode p = head;
        while (p.next != null) {
            //相等则删除
            if (p.next.val == val) {
                p.next = p.next.next;
            } else {
                //不相等则移位
                p = p.next;
            }
        }
        return head;
    }

    public ListNode removeElements2(ListNode head, int val) {
        //删除值相同的头结点后，可能新的头结点也值相等，用循环解决
        while (head != null && head.val == val) {
            head = head.next;
        }
        if (head == null) //這句不能放前面，否則上面一個變成null時無法返回
            return head;
        ListNode prev = head; //确保当前结点后还有结点
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return head;
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
